
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1589. -- [Usaco2008 Dec]Trick or Treat on the Farm -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1589: [Usaco2008 Dec]Trick or Treat on the Farm</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>180&nbsp;&nbsp;<span class=green>Solved: </span>104<br>[<a href='submitpage.php?id=1589'>Submit</a>][<a href='problemstatus.php?id=1589'>Status</a>][<a href='bbs.php?id=1589'>Discuss</a>]</center><h2>Description</h2><div class=content>Every year in Wisconsin the cows celebrate the USA autumn holiday
of Halloween by dressing up in costumes and collecting candy that
Farmer John leaves in the N (1 <= N <= 100,000) stalls conveniently
numbered 1..N.

Because the barn is not so large, FJ makes sure the cows extend
their fun by specifying a traversal route the cows must follow.  To
implement this scheme for traveling back and forth through the barn,
FJ has posted a "next stall number" next_i (1 <= next_i <= N) on
stall i that tells the cows which stall to visit next; the cows
thus might travel the length of the barn many times in order to
collect their candy.

FJ mandates that cow i should start collecting candy at stall i.
A cow stops her candy collection if she arrives back at any stall
she has already visited.

Calculate the number of unique stalls each cow visits before being
forced to stop her candy collection.

定义了一类有向图，每一个结点有且仅有一个后继。现在把从一个节点出发所能够遍历到
的结点数定义为该结点的可遍历长度。现在给定一个有N(0 <= N <= 100 000)个节点的有向图，要求
输出每一个节点的可遍历长度。</div><h2>Input</h2><div class=content>* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer: next_i

</div><h2>Output</h2><div class=content>* Lines 1..N: Line i contains a single integer that is the total
        number of unique stalls visited by cow i before she returns to
        a stall  she has previously visited.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4        //有四个点<br />
1       //1有一条边指向1<br />
3      //2有一条边指向3<br />
2     //3有一条边指向2<br />
3<br />
<br />
INPUT DETAILS:<br />
<br />
Four stalls.<br />
* Stall 1 directs the cow back to stall 1.<br />
* Stall 2 directs the cow to stall 3<br />
* Stall 3 directs the cow to stall 2<br />
* Stall 4 directs the cow to stall 3<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>1<br />
2<br />
2<br />
3<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p>Cow 1:  Start at 1, next is 1.  Total stalls visited: 1.<br />
Cow 2:  Start at 2, next is 3, next is 2.  Total stalls visited: 2.<br />
Cow 3:  Start at 3, next is 2, next is 3.  Total stalls visited: 2.<br />
Cow 4:  Start at 4, next is 3, next is 2, next is 3. Total stalls visited: 3.<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1589'>Submit</a>][<a href='problemstatus.php?id=1589'>Status</a>][<a href='bbs.php?id=1589'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
